class Solution {
public:
    int row, col;
    bool flag[7][7];
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == word[0])
                {
                    flag[i][j] = true;
                    if (dfs(board, word, i, j, 1)) return true;
                    flag[i][j] = false;
                }
            }
        }
        return false;
    }

    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool dfs(vector<vector<char>>& board, string& word, int x, int y, int cur)
    {
        if (cur == word.size()) return true;

        for (int sign = 0; sign < 4; sign++)
        {
            int i = x + dx[sign];
            int j = y + dy[sign];

            if (i >= 0 && i < row && j >= 0 && j < col && flag[i][j] == false && board[i][j] == word[cur])
            {
                flag[i][j] = true;
                if (dfs(board, word, i, j, cur + 1)) return true;
                flag[i][j] = false;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool flag[16][16];
    int row, col;
    int ret = 0;
    int getMaximumGold(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (grid[i][j] != 0)
                {
                    flag[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    flag[i][j] = false;
                }
        return ret;
    }
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
    void dfs(vector<vector<int>>& grid, int x, int y, int count)
    {

        for (int sign = 0; sign < 4; sign++)
        {
            int i = x + dx[sign];
            int j = y + dy[sign];
            if (i < row && i >= 0 && j < col && j >= 0 && flag[i][j] == false && grid[i][j] != 0)
            {
                flag[i][j] = true;
                dfs(grid, i, j, count + grid[i][j]);
                flag[i][j] = false;
            }
        }
        if (count > ret) ret = count;
        return;
    }
};
class Solution {
public:
    bool flag[20][20];
    int row, col;
    int ret = 0;
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };

    int uniquePathsIII(vector<vector<int>>& grid) {
        int size = 0;
        row = grid.size();
        col = grid[0].size();
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (grid[i][j] == 0)
                    size++;
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (grid[i][j] == 1)
                {
                    flag[i][j] = true;
                    dfs(grid, i, j, size);
                    break;
                }
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, int size)
    {
        if (grid[x][y] == 2)
        {
            if (size == 0) ret++;
            return;
        }
        for (int sign = 0; sign < 4; sign++)
        {
            int i = x + dx[sign];
            int j = y + dy[sign];
            if (i < row && i >= 0 && j < col && j >= 0 && flag[i][j] == false && grid[i][j] != -1)
            {
                flag[i][j] = true;
                if (grid[i][j] == 0) dfs(grid, i, j, size - 1);
                else
                {
                    dfs(grid, i, j, size);
                }
                flag[i][j] = false;
            }
        }
    }
};
